/*
 * Copyright (c) 2024. Shanghai HEADING information Engineering Co., Ltd. All rights reserved.
 */
package com.lovely602.algorithm.sort;

/**
 * 通过相邻元素（i 与 i-1）之间的比较和交换，将排序码较小的元素逐渐从底层移向顶层。整个 过程像水底的气泡逐渐向上冒由此而得名。
 *
 * <p>冒泡排序的算法原理
 * <p>1）比较相邻的元素，如果第一个比第二个大，就交换他们两个。
 * <p>2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，在这一点，最后的元素应该会是最大的数。
 * <p>3）针对所有的元素重复以上的步骤，除了最后一个。
 * <p>4）持续对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 * <p>
 * 冒泡排序时间复杂度为 O(n²)。
 * <a href="https://www.dotcpp.com/course/894">课程地址</a>
 *
 * @author lizhixing
 */
public class BubbleSort {

  public static void main(String[] args) {
    int[] data = { 43, 55, 70, 30, 5, 8 };
    print(data);
    bubbleSort(data);
    print(data);
  }

  //冒泡排序
  public static void bubbleSort(int[] arr) {
    //外层循环用来控制数组循环的圈数
    for (int i = 0; i < arr.length - 1; i++) {
      //内层循环用来完成元素值比较，把大的元素值互换到后面
      for (int j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

  public static void print(int[] data) {
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }

}
